import java.util.*;

import javafx.util.*;
/*
Dijkstra求最短路I
给定一个 n个点 m条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1号点到 n号点的最短距离，如果无法从 1号点走到 n号点，则输出 −1。

输入格式
第一行包含整数 n和 m。
接下来 m行每行包含三个整数 x,y,z，表示存在一条从点 x到点 y的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。

数据范围
1≤n≤500,1≤m≤1e5, //稠密图
图中涉及边长均不超过10000。

输入样例：
3 3
1 2 2
2 3 1
1 3 4

输出样例：
3
 */
public class Main {
    static int n, m;
    static int[][] graph = new int[501][501];
    static int[] dist = new int[501];
    static boolean[] visited = new boolean[501];

    static void dijkstra() {
        for (int i = 1; i <= n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!visited[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            visited[t] = true;
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + graph[t][j]);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i <= n; i++) {
            dist[i] = 0x3f3f3f3f;
            for (int j = 0; j <= n; j++) {
                graph[i][j] = 0x3f3f3f3f;
            }
        }
        dist[1] = 0;

        for (int i = 1; i <= m; i++) {
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            graph[x][y] = Math.min(graph[x][y], z);
        }
        dijkstra();
        if (dist[n] == 0x3f3f3f3f) {
            System.out.println("-1");
        } else System.out.println(dist[n]);
    }
}

/*
Dijkstra求最短路II
给定一个 n个点 m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1号点到 n号点的最短距离，如果无法从 1号点走到 n号点，则输出 −1。

输入格式
第一行包含整数 n和 m。
接下来 m行每行包含三个整数x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1号点到 n号点的最短距离。
如果路径不存在，则输出−1。

数据范围
1≤n,m≤1.5×1e5, //稀疏图
图中涉及边长均不小于 0，且不超过10000。
数据保证：如果最短路存在，则最短路的长度不超过 1e9。

输入样例：
3 3
1 2 2
2 3 1
1 3 4

输出样例：
3

 */
//public class Main {
//    static int n, m;
//    static int[] distance = new int[100010];
//    static boolean[] visited = new boolean[100010];
//    static ArrayList<ArrayList<Pair<Integer, Integer>>> graph = new ArrayList<>();
//
//    static void dijkstra() {
//        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(
//                Comparator.comparingInt(Pair::getValue)
//        );//pair(vertex,distance)
//        pq.add(new Pair<>(1, 0));
//        while (!pq.isEmpty()) {
//            Pair<Integer, Integer> pair = pq.poll();
//            int v = pair.getKey(), d = pair.getValue();//vertex,distance
//            if (visited[v]) continue;
//            visited[v] = true;
//            for (Pair<Integer, Integer> edge : graph.get(v)) {
//                int otherV = edge.getKey(), otherD = edge.getValue();
//                if (distance[otherV] > d + otherD) {
//                    distance[otherV] = d + otherD;
//                    pq.add(new Pair<>(otherV, distance[otherV]));
//                }
//            }
//        }
//
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        n = sc.nextInt();
//        m = sc.nextInt();
//        for (int i = 0; i <= n; i++) {
//            graph.add(new ArrayList<>());
//            distance[i] = 0x3f3f3f3f;
//        }
//        for (int i = 1; i <= m; i++) {
//            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
//            graph.get(x).add(new Pair<>(y, z));
//        }
//        dijkstra();
//        if (distance[n] == 0x3f3f3f3f) {
//            System.out.println("-1");
//        } else System.out.println(distance[n]);
//    }
//}